是否有一个函数获取列表并返回该列表中重复元素的列表?

2023-03-27 08:08| 来源: 网络整理| 查看: 265

百度翻译此文有道翻译此文问题描述

Is there a Haskell function that takes a list and returns a list of duplicates/redundant elements in that list?

I'm aware of the the nub and nubBy functions, but they remove the duplicates; I would like to keep the dupes and collects them in a list.

推荐答案

Is there a Haskell function that takes a list and returns a list of duplicates/redundant elements in that list?

You can write such a function yourself easily enough. Use a helper function that takes two list arguments, the first one of which being the list whose dupes are sought; walk along that list and accumulate the dupes in the second argument; finally, return the latter when the first argument is the empty list.

dupes l = dupes' l [] where dupes' [] ls = ls dupes' (x:xs) ls | not (x `elem` ls) && x `elem` xs = dupes' xs (x:ls) | otherwise = dupes' xs ls

Test:

λ> dupes [1,2,3,3,2,2,3,4] [3,2]

Be aware that the asymptotic time complexity is as bad as that of nub, though: O(n^2). If you want better asymptotics, you'll need an Ord class constraint.

其他推荐答案

The simplest way to do this, which is extremely inefficient, is to use nub and \\:

import Data.List (nub, (\\)) getDups :: Eq a => [a] -> [a] getDups xs = xs \\ nub xs

If you can live with an Ord constraint, everything gets much nicer:

import Data.Set (member, empty, insert) getDups :: Ord a => [a] -> [a] getDups xs = foldr go (const []) xs empty where go x cont seen | member x seen = x : r seen | otherwise = r (insert x seen) 其他推荐答案

I wrote these functions which seems to work well.

The first one return the list of duplicates element in a list with a basic equlity test (==)

duplicate :: Eq a => [a] -> [a] duplicate [] = [] duplicate (x:xs) | null pres = duplicate abs | otherwise = x:pres++duplicate abs where (pres,abs) = partition (x ==) xs

The second one make the same job by providing a equality test function (like nubBy)

duplicateBy :: (a -> a -> Bool) -> [a] -> [a] duplicateBy eq [] = [] duplicateBy eq (x:xs) | null pres = duplicateBy eq abs | otherwise = x:pres++duplicateBy eq abs where (pres,abs) = partition (eq x) xs

【本文地址】

公司简介

联系我们